"""
从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。
然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
"""


def dfs(graph, s, S=None, res=None):
    if S is None:
        S = set()
    if res is None:
        res = []

    res.append(s)
    S.add(s)
    for u in G[s]:
        if u in s:
            continue
        S.add(u)
        dfs(graph, u, S, res)

    return res


if __name__ == '__main__':
    G = {'0': ['1', '2'],
         '1': ['2', '3'],
         '2': ['3', '5'],
         '3': ['4'],
         '4': [],
         '5': []}
    print(dfs(G, '0'))
